package com.cshawn.leetcodes.sword;

/**
 * 二进制中1的个数
 * 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。
 * 例如，把 9表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 * 示例 1：
 * 输入：00000000000000000000000000001011
 * 输出：3
 * 解释：输入的二进制串 00000000000000000000000000001011中，共有三位为 '1'。
 *
 * 示例 2：
 * 输入：00000000000000000000000010000000
 * 输出：1
 * 解释：输入的二进制串 00000000000000000000000010000000中，共有一位为 '1'。
 *
 * 示例 3：
 * 输入：11111111111111111111111111111101
 * 输出：31
 * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
 *
 * 提示：
 * 输入必须是长度为 32 的 二进制串 。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author C.Shawn
 * @date 2020/11/24 8:50
 */
public class Sword_15 {
    /**
     * 1. 最简单的方法：与1相与为1则末位为1，再将数向右移1位，再次重复，直到数字变为0
     * 2. 另外一种方法：假设末尾有几个0，那么减1后，这些0都变成1，最后一个1变成0，此时两数相与，可以将最后一个1消除。
     *      那么，按照这种方法重复直到数字变为0，即将全部的1消除，统计可得1的个数。
     */
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & n - 1;
            count++;
        }
        return count;
    }
}
